import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * @Author: wenjingyuan
 * @Date: 2022/01/05/20:15
 * @Description:基于int的最大堆
 */
public class MaxHeap {
   private List<Integer> data;
   public MaxHeap(){
     this(15);
   }
   public MaxHeap(int initcap){
      data=new ArrayList<>(initcap);
   }

    /**
     * 根据孩子节点的索引求得父亲节点
     * @param k
     * @return
     */
   public int parent(int k){
       return (k-1)>>1;
   }

    /**
     * 根据父亲的节点求得左孩子的节点
     * @param i
     * @return
     */
   public int leftChild(int i){
      return 2*i+1;
   }

    /**
     * 根据父亲的节点求得右孩子的节点
     * @param i
     * @return
     */
   public int rightChild(int i){
       return 2*i+2;
   }

    /**
     *取出最大值
     * @return
     */
   public int extractMax(){
       //先需要判断这个堆是否为空
       if (data.size()==0){
           //抛出异常
           throw new NoSuchElementException("heap is empty!");
       }
       int max=data.get(0);
       data.set(0, data.get(data.size()-1));
       data.remove(data.size()-1);
       siftDown(0);
       return max;
   }

    /**
     * 下沉操作
     * @param i
     */
    private void siftDown(int i) {
        // 当i还有子树时，说明还没判断结束
        // 若左孩子都不存在，一定不存在右孩子
        while (leftChild(i)< data.size()){
            int j=leftChild(i);
            if(j+1< data.size()&&data.get(j+1)> data.get(j)){
                //保证了j此时就是孩子中最大节点
                j=j+1;
            }
            if (data.get(i)>=data.get(j)){
                break;
            }else{
                swap(i,j);
                i=j;
            }
        }
    }

    //堆化heapify
   public MaxHeap(int[] arr){
        //先将arr所有元素拷贝到data中
        data=new ArrayList<>(arr.length);
        for(int i: arr){
            data.add(i);
        }
       //从最后一个非叶子节点开始进行元素下沉
       for (int i = parent(data.size()-1); i >= 0 ; i--) {
           siftDown(i);
       }
   }
    //添加元素
   public void add(int value){
       //在数组末尾添加元素
       data.add(value);
       //利用siftUp操作再次构成最大堆
       siftUp(data.size()-1);
   }

    /**
     * 元素的上浮操作
     * @param k
     */
    private void siftUp(int k) {
       //当走到k=0
       //当孩子节点的值小于父节点的值
       while(k>0 && data.get(k)>data.get(parent(k))){
           swap(k,parent(k));
           k=parent(k);
       }
    }

    /**
     * 交换当前k和parent的值
     * @param k
     * @param parent
     */
    private void swap(int k, int parent) {
        int temp=data.get(k);
        data.set(k,data.get(parent));
        data.set(parent,temp);
    }

    @Override
    public String toString() {
        return data.toString();
    }
    //添加操作
//    public static void main(String[] args) {
//        int [] test={20,18,75,68,95,46,30,51,45,48,53};
//        MaxHeap heap=new MaxHeap(test.length);
//        for (int i = 0; i < test.length; i++) {
//            heap.add(test[i]);
//        }
//        System.out.println(heap);
//    }
    //取出最大元素
//    public static void main(String[] args) {
//        int [] test={20,18,75,68,95,46,30,51,45,48,53};
//        MaxHeap heap=new MaxHeap(test.length);
//        for (int i = 0; i < test.length; i++) {
//            heap.add(test[i]);
//        }
//        for (int i = 0; i <test.length ; i++) {
//            test[i]=heap.extractMax();
//        }
//        System.out.println(Arrays.toString(test));
//    }
    //堆化测试
    public static void main(String[] args) {
        int[] data = {20,18,75,68,95,46,30,51,45,48,53};
        MaxHeap heap = new MaxHeap(data);
        for (int i = 0; i < data.length; i++) {
            data[i] = heap.extractMax();
        }
        System.out.println(Arrays.toString(data));
    }


}
